package _3_leetcode_41_60._41缺失的第一个正数;

/**
 * User: Mazexal
 * Date: 2021/1/30
 */
public class Solution {


    public static void main(String[] args) {
        System.out.println(firstMissingPositive(new int[]{1, 2, 0}));
        System.out.println(firstMissingPositive(new int[]{3, 4, -1, 1}));
        System.out.println(firstMissingPositive(new int[]{7, 8, 9, 11, 12}));
    }

    // 原地哈希
    // 这里最差情况就是1-n全满, 所以返回N+1,
    // 如果不是这样的话, 说明中间有空位, 可以返回空位
    // 原理就是遍历数组, 将1-n里存在的数组设为负数, 然后遍历1-n, 发现不是负数的直接返回 N+1
    public static int firstMissingPositive(int[] nums) {
        int n = nums.length;
        // 如果里面有数组是小于等于0的, 直接设置为n+1, 下一步操作就可以直接跳过
        // 这里可以进行一次优化, 如果没有存在1的, 直接返回1
        boolean hasOne = false;
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
            if (hasOne || nums[i] == 1) {
                hasOne = true;
            }
        }
        if(!hasOne){
            return 1;
        }
        // 这里把所有 1-n 之间数组的数值进行逆转为负数
        for (int i = 0; i < n; i++) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }

        // 这里检查 1-n 之间的数组
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        // 因为是下标, 所以返回为N+1
        return n + 1;
    }

}
